package linearstructure.stack.calculator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-02 19:26
 * @ Description : 对后缀表达式求值
 */
public class ReversePoland
{
    public static void main(String[] args)
    {
        String infixExpr = "1+((2+3)*4)-5";
        List<String> infixListString = getInfixListString(infixExpr);
        //System.out.println("infixListString = " + infixListString);

        List<String> suffixListString = parseSuffixListString(infixListString);
        //System.out.println("suffixListString = " + suffixListString);

        int res = calculate(suffixListString);
        System.out.println("res = " + res);
    }

    //将前缀表达式转为字符串集合
    public static List<String> getInfixListString(String infixExpr)
    {
        List<String> list = new ArrayList<>();
        int i = 0;
        String str;
        char c;
        do
        {
            if ((c = infixExpr.charAt(i)) < 48 || (c = infixExpr.charAt(i)) > 57)
            {
                list.add("" + c);
                ++i;
            }
            else
            {
                str = "";
                //考虑多位数
                while (i < infixExpr.length()
                        && ((c = infixExpr.charAt(i)) >= 48)
                        && ((c = infixExpr.charAt(i)) <= 57))
                {
                    str += c;
                    ++i;
                }
                list.add(str);
            }

        } while (i < infixExpr.length());

        return list;

    }

    //将前缀表达式集合转为后缀表达式集合
    public static List<String> parseSuffixListString(List<String> infixList)
    {
        Stack<String> stack = new Stack<>();//符号栈
        List<String> list = new ArrayList<>();

        for (String item : infixList)
        {
            if (item.matches("\\d+"))
            {
                list.add(item);
            }
            else if (item.equals("("))
            {
                stack.push(item);
            }
            else if (item.equals(")"))
            {
                while (!stack.peek().equals("("))
                {
                    list.add(stack.pop());
                }
                stack.pop();//弹出"("
            }
            else
            {
                //当前运算符优先级 <= stack栈顶运算符优先级
                while (stack.size() != 0
                        && Operator.getVal(stack.peek()) >= Operator.getVal(item))
                {
                    list.add(stack.pop());
                }
                stack.push(item);
            }
        }
        //将stack中剩余的运算符放入list
        while (stack.size() != 0)
        {
            list.add(stack.pop());
        }

        return list;
    }


    public static List<String> getSuffixListString(String suffixExpr)
    {
        String[] split = suffixExpr.split(" ");

        return new ArrayList<>(Arrays.asList(split));
    }

    public static int calculate(List<String> ls)
    {
        Stack<String> stack = new Stack<>();
        for (String item : ls)
        {
            if (item.matches("\\d+"))
            {
                stack.push(item);
            }
            else
            {
                //运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                switch (item)
                {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("运算符有误");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

}

class Operator
{
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 1;
    private static final int DIV = 1;

    public static int getVal(String operator)
    {
        int res = 0;
        switch (operator)
        {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return res;
    }


}